package com.dataStructure.并查集;


import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

@SuppressWarnings("all")
public class 通用的并查集_带泛型<V> {
    private Map<V, Node<V>> nodes = new HashMap<>();

    public void makeSet(V v) {
        if (nodes.containsKey(v)) return;
        nodes.put(v,new Node<>(v));
    }

    //找出v的根节点
    private Node<V> findNode(V v) {
        Node<V> node = nodes.get(v);
        if (node == null) return null;

        //参照路径减半优化
        while (!Objects.equals(node.value,node.parent.value)){
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

    //传V 返回V的根节点V
    public V find(V v) {
        return findNode(v) == null ? null : findNode(v).value;
    }

    public void union(V v1, V v2) {
        Node<V> p1 = findNode(v1);
        Node<V> p2 = findNode(v2);
        if (p1 == null || p2 == null) return;
        if (Objects.equals(p1.value,p2.value)) return;

        //比较两棵树的高度
        if (p1.rank < p2.rank){
            //如果p1的高度小于p2的高度，则将p1嫁接到p2上
            p1.parent = p2;
        } else if (p1.rank > p2.rank) {
            //如果p1的高度大于p2的高度，则将p2嫁接到p1上
            p2.parent = p1;
        }else {
            //如果两棵树的高度一样高，则随意嫁接即可，并将被嫁接的树高度加一
            p1.parent = p2;
            p2.rank += 1;
        }
    }

    public boolean isSame(V v1, V v2) {
        return Objects.equals(find(v1), find(v2));
    }

    private static class Node<V> {
        public Node(V value) {
            this.value = value;
        }

        //数据
        V value;

        //parent指针指向自己
        Node<V> parent = this;

        //当前节点的高度，初始为1
        int rank = 1;
    }
}
